package compiler.tac;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

import compiler.dot.GraphHelper;
import compiler.symboltable.SymbolTable;
import compiler.symboltable.SymbolTable.Item;
import compiler.symboltable.SymbolTable.ItemType;

public class ThreeAddressCode {
	public static final String returnTemp = "t_r"; // a reserved temp variable for return value: like %eax, %edx
	
	private EntryBlock entry;
	private BasicBlock exit;
	
	private ArrayList<BasicBlock> blocks;
	
	private ArrayList<ThreeAddressCode> children;
	private ThreeAddressCode parent;
	private SymbolTable st;
	int tempCnt = 0;
	int lableCnt = 0;
	
	public void setST(SymbolTable st)
	{
		this.st = st;
	}
	public EntryBlock getEntry()
	{
		return entry;
	}
	public BasicBlock getExit()
	{
		return exit;
	}
	public SymbolTable getST()
	{
		return this.st;
	}
	
	public ThreeAddressCode()
	{
		blocks = new ArrayList<BasicBlock>();
		children = new ArrayList<ThreeAddressCode>();
	}
	
	public void addParent(ThreeAddressCode p)
	{
		parent = p;
	}
	public void addEmptyBlock()
	{
		ArrayList<BasicBlock> allblocks = getAllBlocks();
		if(allblocks!=null)
			for(int i = 0; i < allblocks.size(); i ++)
			{
				if(allblocks.get(i).getPreds().size() > 1 && allblocks.get(i).getSuccs().size() > 1)
					allblocks.get(i).addPreEmptBlock(this);
			}
	}
	public void addChildren(ThreeAddressCode c)
	{
		children.add(c);
	}
	public ArrayList<ThreeAddressCode> getChildren()
	{
		return children;
	}
	
	public void buildDominatorTree() {
		for (ThreeAddressCode child : children) {
			child.buildDominatorTree();
		}
		addEmptyBlock();
		resetdom();
		HashMap<BasicBlock, HashSet<BasicBlock>> domRel = new HashMap<BasicBlock, HashSet<BasicBlock>>();
		
		HashSet<BasicBlock> all = new HashSet<BasicBlock>(blocks);
		all.add(entry);
		all.add(exit);
		
		// initialize domRel
		HashSet<BasicBlock> rootDom = new HashSet<BasicBlock>();
		rootDom.add(entry);
		domRel.put(entry, rootDom);
		
		for (BasicBlock block : blocks) {
			HashSet<BasicBlock> dom = new HashSet<BasicBlock>(all);
			domRel.put(block, dom);
		}		
		
		HashSet<BasicBlock> exitDom = new HashSet<BasicBlock>(all);
		domRel.put(exit, exitDom);
		
		// build domRel
		boolean change;
		do {
			change = false;
			for (BasicBlock block : all) {
				if (block == entry) {
					continue;
				}
				HashSet<BasicBlock> dom = new HashSet<BasicBlock>(all);
				for (BasicBlock pred : block.getPreds()) {
					dom.retainAll(domRel.get(pred));
				}
				dom.add(block);
				if (!dom.equals(domRel.get(block))) {
					change = true;
					domRel.put(block, dom);
				}
			}
		} while (change);
		
		// build dominator tree
		HashSet<BasicBlock> remainAll = new HashSet<BasicBlock>(all);
		
		LinkedList<BasicBlock> workset = new LinkedList<BasicBlock>();
		workset.offer(entry);
		remainAll.remove(entry);
		while (!workset.isEmpty()) {
			BasicBlock n = workset.poll();
			for (BasicBlock p : remainAll) {
				if (p == n) {
					continue;
				}
				HashSet<BasicBlock> domP = domRel.get(p);
				domP.remove(n);
				if (domP.size() == 1 && domP.contains(p)) {
					n.addDomChild(p);
					workset.offer(p);
				}
			}
			remainAll.removeAll(workset);
		}
	}
	
	public void resetdom()
	{
		for(BasicBlock b: this.blocks)
		{
			b.domChildren = new ArrayList<BasicBlock>();
			b.domF = new ArrayList<BasicBlock>();
		}
	}
	public void calDomF()
	{
		for(ThreeAddressCode child : children)
			child.calDomF();
		this.entry.calDomF();
	}
	
	public void toSSAForm() {
		if(children!=null && children.size() > 0)
			for(ThreeAddressCode func : children)
				func.toSSAForm();
		for(Item v : this.st.getTable())
		{
			if(v.getType() != ItemType.FUNC && v.getType() != ItemType.ARRAY)
			{
				insertFi(v);
				rename(v);
			}
		}
		if(this.getST().getParent() != null)
			for(Item v: this.getST().getParent().getTable())
				if(this.getST().position(v.getName())==-1 && v.getType() != ItemType.FUNC && v.getType() != ItemType.ARRAY)
				{
					//System.out.println("use variable from father " + v.getName());
					insertFi(v);
					rename(v);
				}	
	}
	
	private void insertFi(Item v)
	{
		//preparing worklist to contain blocks which assign values to V
		ArrayList<BasicBlock> worklist = new ArrayList<BasicBlock>();
		ArrayList<Boolean> dFplus = new ArrayList<Boolean>();
		for(BasicBlock b : blocks)
		{
			if(b.containAssigntoV(v))
				worklist.add(b);
	
			dFplus.add(false);
		}
		
		while(worklist.size()!=0)
		{
			BasicBlock b = worklist.get(0);
			for(BasicBlock df: b.getDomF())
			{
				if(dFplus.get(blocks.indexOf(df))==false)
				{
					df.addPhiInstruction(v.getName(),df.getPreds().size());
					dFplus.set(blocks.indexOf(df), true);
					if(worklist.indexOf(df)==-1)
						worklist.add(df);
				}
			}
			worklist.remove(0);
		}
	}
	
	private void rename(Item v)
	{
		int curCount = 0;
		//ArrayList<Integer> stack = new ArrayList<Integer>();
		NameStack stack = new NameStack();
		stack.push(curCount);
		entry.rename(v, curCount, stack);
		//System.out.println("22222222 " + entry.successors.get(0).getDomChildren().size());
	}
	public String getTempVar() {
		String ret = "t_"+String.valueOf(tempCnt);
		tempCnt++;
		return ret;
	}
	
	public String getLable()
	{
		if (parent != null) {
			return parent.getLable();
		} else {		
			String ret = "L"+ String.valueOf(lableCnt);
			lableCnt ++;
			return ret;
		}
	}
	
	public void printCFG(GraphHelper graph) {
		// functions
		for (ThreeAddressCode child : children) {
			child.printCFG(graph);
		}

		// module body
		entry.printCFG(graph);
	}
	
	public void printDT(GraphHelper graph) {
		for (ThreeAddressCode child : children) {
			child.printDT(graph);
		}
		
		entry.printDT(graph);
	}
	
	public int addBlock(BasicBlock b) {
		int ret = blocks.indexOf(b);
		if (ret == -1) {
			ret = blocks.size();
			blocks.add(b);
		}
		
		b.setOrder(ret);
		
		return ret;
	}

	public void setEntry(EntryBlock e) {
		entry = e;
	}
	
	public void setExit(BasicBlock e) {
		exit = e;
	}
	
	public void printTAC(PrintStream out)
	{
		for(ThreeAddressCode child : children) {
			child.printTAC(out);
		}

		out.print("\n"+entry.name+":");
		for(BasicBlock bb : blocks)
		{
			if(bb.getLable() != null)
				out.print(bb.getLable()+":");
			for(Instruction inst : bb.getInstructions())
			{
				String result = inst.toString();
				out.println(result);
			}
		}
	}

	public ArrayList<BasicBlock> getAllBlocks() {
		return blocks;
	}
}
